package com.leetcode.linkedList;

import com.leetcode.basic.ListNode;

/**
 * @author Dennis Li
 * @date 2020/7/30 20:36
 */
public class RotateRight_61 {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        ListNode fast = head;
        while (k-- > 0) {
            fast = fast.next == null ? head : fast.next;
        }
        if (fast == head) return head;
        else if (fast.next != null) {
            ListNode newHead = fast.next, pre = newHead;
            // 从尾部插入
            while (pre.next != null) {
                pre = pre.next;
            }
            pre.next = head;
            fast.next = null;
            return newHead;
        } else {
            ListNode newHead = head.next;
            fast.next = head;
            head.next = null;
            return newHead;
        }
    }

    public ListNode rotateRight2(ListNode head, int k) {
        if (head == null || head.next == null || k == 0)
            return head;
        ListNode fast = head, slow = head;
        int count = 1;
        while (k-- > 0) {
            // 遍历完一圈
            if (fast.next == null) {
                // 避免反复遍历链表
                k = k % count;
                fast = head;
            } else {
                count++;
                fast = fast.next;
            }
        }
        // 如果走回链表头部，那么代表不需要移动
        if (fast == head) return head;
        // 通过一对快慢指针找到截断的位置
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        ListNode newHead = slow.next, pre = newHead;
        // 从尾部插入
        while (pre.next != null) {
            pre = pre.next;
        }
        pre.next = head;
        slow.next = null;
        return newHead;
    }

}
